\section{Strengthened clique lifting procedure}

We propose to strengthen the clique lifting procedure as follows (the proof
using the Lifting Lemma from~\cite{XavierCampelo11} is omitted due
to space limitation).

\begin{lemma}
Let $t \in \{ 0, \ldots, r \}$, $F_0 := STAB(G)$, $F_t := \{ x
\in F_{t-1} \mid x_{W_t} = 1 \}$ if $t > 0$, and $\mathcal S_t := \mathcal
S(G) \cap F_t$. Then, $f_t(x) \leq 1$ is valid for $F_t$, where $f_t(x) :=
x_{W_{r+1}}$ if $t=r$ or
$f_t(x) := f_{t+1}(x) + \phi_{t+1} (x_{W_{t+1}} -
1)$ otherwise, and
$
\phi_{t+1} := \max \Big\{ \{ 0 \} \cup \big\{ f_{t+1}(x) - 1 \mid
x \in \mathcal S_t, x_{W_{t+1}} = 0 \big\} \Big\}.
$
\label{lem:stlifting}
\end{lemma}

This iterative procedure may generate stronger
valid inequalities than the procedure in~\cite{Correa14}. For instance, for the
example in Fig.~\ref{fig:lifting}, $x_{\{ 4, 5, 6, 7, 8 \}} +
2x_{\{1, 2, 3 \}} \leq 3$ is a linear combination between $x_{\{1, 2, 4, 6,
7, 8\}} + 2x_{\{3\}} \leq 2$ and the clique inequality $x_{\{1,2,5\}} \leq
1$. Indeed, it can be shown that this new procedure generates facet defining
inequalities for $STAB(G)$ if there exists $k > 0$ such that the following conditions hold, for all $t \in \{ 1, \ldots, r \}$ (see~\cite{XavierCampelo11} for more details):
\begin{enumerate}[label=(\Roman*),ref=\Roman*]
  \item $|W_t| = k$ and the subgraph of $G_{t-1}$ induced by $\bigcup_{i=1}^t
  W_i$ is $k$-partite with vertex classes $V_t^1, \ldots, V_t^k$,
  \label{it:Wk1}
  \item $T_t := (V_t, \mathcal W_t)$ is a $k$-uniform strong hypertree
  defined by $V_t := \bigcup_{i=1}^k V_t^i$ and $\mathcal W_t := \{ W_1,
  \ldots, W_t \}$,
  \item for every $i \in \{ 1, \ldots, k-1 \}$ and $w \in V_r^0$ such that
  $N_{G_r}(w) \cap V_r^i \ne \emptyset$, one of the following holds: $v \in W_t \cap V_t^i$ is a
  neighbor of $w$ in $G$ or there exists $t' \in \{ 1, \ldots, r \}$ such that $W_t$ is a clique of
  $G_{t'-1}$, $W_t$ and $W_{t'}$ are adjacent in $T_r$, $v \not\in W_{t'}$,
  and $v' \in W_{t'} \cap V_r^i$ is a neighbor of $w$ in $G_{t'-1}$,
  \label{it:noclique1}
  \item every $v \in V_t^k$ has no neighbors in $V_r^0$, {\em i.e.} $N_{G_r}(v)
  \cap V_r^0 = \emptyset$,
  \label{it:VkV01}
\end{enumerate}
considering that $W_{r+1}$ is a maximal clique of
$G_r$ such that $W_{r+1} \cap V_r^k = \emptyset$. The example in
Fig.~\ref{fig:projection}--\ref{fig:lifting} satisfies these conditions, with
$k=r=3$, $V^0_3 = \{ 6, 7, 8 \}$, $V^1_3 = \{ 2, 4 \}$, $V^2_3 = \{ 3, 5
\}$, and $V^3_3 = \{ 1 \}$, which means that the generated inequality
$x_{\{1,2,4,6,7,8\}} + 2x_{\{3\}} \leq 2$ is facet defining for $STAB(G)$.
Conditions~\eqref{it:Wk1}--\eqref{it:VkV01} differ from those
in~\cite{XavierCampelo11} in two points. First, the
subsets $W_3, \ldots, W_r$ are not required to be cliques in $G$. Second, we assume condition~\eqref{it:noclique} to impose appropriate false edges in
$G_{t'}$ instead of the auxiliary contracted graph defined
in~\cite{XavierCampelo11} to determine $W_{r+1}$.
%
%, the subsets $W_3, \ldots, W_r$ are not required to be cliques in $G$ in our
% case (we use condition~\eqref{it:noclique1} instead to impose appropriate false edges in
%$G_{t'}$).
%
 %These conditions differ from
%those in~\cite{XavierCampelo11} in two points. First, we do not ask for the
%subsets $W_3, \ldots, W_r$ to be cliques in $G$. Second, we use clique
%projection and we assume condition~\eqref{it:noclique} and the special
%condition on $W_{r+1}$ instead of the auxiliary contracted graph defined
% in~\cite{XavierCampelo11}.
%
The related proofs, inspired in~\cite{XavierCampelo11}, are omitted due to space limitation.

\begin{figure}[htbp]
\centering
        \begin{subfigure}[{$g_3(x) = x_{W_4} \leq 1$
        is valid for $STAB(G_2)$ since $\gamma_3 = 0$. This comes from
        $\gamma_3 = \max \left\{ g_3(x) \mid x_{W_3} = 0 \right\} -
        1$, which has $\{ 8 \}$ as an optimum solution}.]{\label{sfig:cl1}
        \quad\begin{tikzpicture}[thick,fill
        opacity=0.5,scale=0.4,font=\scriptsize]
\shade[rounded corners=1ex,fill=red,above] (1.north west) to[out=150,in=-60]
(2.south east) -- (3.base) -- (3.south) -- cycle;
\node[text=red,text opacity=1] at +(-3,0) {$W_1$}; 
\shade[rounded corners=1ex,fill=blue,above] (1.north) -- (3.south east) --
(3.base) -- (4.base) -- (4.south west) -- cycle;
\node[text=blue,text opacity=1] at +(0,-1) {$W_2$}; 
\shade[rounded corners=1ex,fill=green,above] (1.north east) to[out=30,in=-120]
(5.south west) -- (4.base) -- (4.south) -- cycle;
\node[text=olive,text opacity=1] at +(3,0) {$W_3$}; 
\shade[rounded corners=1ex,fill=orange,above] (2.north west) --
(5.north east) -- (5.south east) -- (2.south west) -- cycle;

			\input{graphExample2}
\draw		(2) 	to[out=40,in=140] (5);

\node[vertex,ball color=green,opaque] (8) at (3.0,3.0) {8};

\draw[very thick,color=red]		(5) 	to[out=145,in=35] (6);
\draw[very thick,color=red]		(5) 	to[out=150,in=30] (7);
\draw[very thick,color=red]		(4) 	-- (5);
\draw[very thick,color=red]		(4) 	-- (6);

\draw[very thick,color=blue]	(2) 	to[out=30,in=150] (7);
\draw[very thick,color=blue]	(2) 	to[out=35,in=145] (8);
\end{tikzpicture}\quad}
        \end{subfigure}\quad\quad
        \begin{subfigure}[Lifting {$f_3(x) = x_{W_4} \leq 1$
        with $\phi_3 = -1$} generates {$f_2(x) = x_{\{2,6,7,8\}} - x_{\{1,4\}}
        \leq 0$}, which is valid for $F_2 = \{ x \in STAB(G) \mid x_{W_1} = x_{W_2} = 1 \}$.]{ \label{sfig:scl1}
        \quad\begin{tikzpicture}[thick,fill
        opacity=0.5,scale=0.4,font=\scriptsize]
\shade[rounded corners=1ex,fill=red,above] (1.north west) to[out=150,in=-60]
(2.south east) -- (3.base) -- (3.south) -- cycle;
\node[text=red,text opacity=1] at +(-3,0) {$W_1$}; 
\shade[rounded corners=1ex,fill=blue,above] (1.north) -- (3.south east) --
(3.base) -- (4.base) -- (4.south west) -- cycle;
\node[text=blue,text opacity=1] at +(0,-1) {$W_2$}; 
\shade[rounded corners=1ex,fill=green,above] (1.north east) to[out=30,in=-120]
(5.south west) -- (4.base) -- (4.south) -- cycle;
\node[text=olive,text opacity=1] at +(3,0) {$W_3$}; 
\shade[rounded corners=1ex,fill=orange,above] (2.north west) --
(5.north east) -- (5.south east) -- (2.south west) -- cycle;

			\input{graphExample2}
\draw		(2) 	to[out=40,in=140] (5);

\node[vertex,ball color=green,opaque] (3) at (-1.5,0) {3};

\draw[very thick,color=red]		(5) 	to[out=145,in=35] (6);
\draw[very thick,color=red]		(5) 	to[out=150,in=30] (7);
\draw[very thick,color=red]		(4) 	-- (5);
\draw[very thick,color=red]		(4) 	-- (6);

\draw[very thick,color=blue]	(2) 	to[out=30,in=150] (7);
\draw[very thick,color=blue]	(2) 	to[out=35,in=145] (8);
\end{tikzpicture}\quad}
        \end{subfigure}
        \begin{subfigure}[Lifting
        {$g_2(x) = g_3(x) \leq 1$} with
        $\gamma_2 = \max \left\{ g_2(x) \mid x_{W_2} = 0 \right\} -
        1 = 1$ results in $g_1(x) = g_2(x) + x_{W_2} \leq 2$, valid for
        $STAB(G_1)$.]{		\label{sfig:cl2}
        \quad\begin{tikzpicture}[thick,fill
        opacity=0.5,scale=0.4,font=\scriptsize]
\shade[rounded corners=1ex,fill=red,above] (1.north west) to[out=150,in=-60]
(2.south east) -- (3.base) -- (3.south) -- cycle;
\node[text=red,text opacity=1] at +(-3,0) {$W_1$}; 
\shade[rounded corners=1ex,fill=blue,above] (1.north) -- (3.south east) --
(3.base) -- (4.base) -- (4.south west) -- cycle;
\node[text=blue,text opacity=1] at +(0,-1) {$W_2$}; 
\shade[rounded corners=1ex,fill=orange,above] (2.north west) --
(5.north east) -- (5.south east) -- (2.south west) -- cycle;

			\input{graphExample2}
\draw		(2) 	to[out=40,in=140] (5);
 
\node[vertex,ball color=blue,opaque] (2) at (-6.0,3.0) {2};
\node[vertex,ball color=blue,opaque] (7) at (0,3.0) {7};

\draw[very thick,color=red]		(5) 	to[out=145,in=35] (6);
\draw[very thick,color=red]		(5) 	to[out=150,in=30] (7);
\draw[very thick,color=red]		(4) 	-- (5);
\draw[very thick,color=red]		(4) 	-- (6);
\end{tikzpicture}\quad}
        \end{subfigure}\quad\quad
        \begin{subfigure}[Lifting
        {$f_2(x) \leq
        0$} with $\phi_2 = 2$ gives {$f_1(x) = x_{\{1,2,4,6,7,8\}} +
        2x_{\{3\}} \leq 2$}, valid for $F_1 = \{ x \in STAB(G) \mid x_{W_1} = 1 \}$.]{ \label{sfig:scl2} 
        \quad\begin{tikzpicture}[thick,fill
        opacity=0.5,scale=0.4,font=\scriptsize]
\shade[rounded corners=1ex,fill=red,above] (1.north west) to[out=150,in=-60]
(2.south east) -- (3.base) -- (3.south) -- cycle;
\node[text=red,text opacity=1] at +(-3,0) {$W_1$}; 
\shade[rounded corners=1ex,fill=blue,above] (1.north) -- (3.south east) --
(3.base) -- (4.base) -- (4.south west) -- cycle;
\node[text=blue,text opacity=1] at +(0,-1) {$W_2$}; 
\shade[rounded corners=1ex,fill=orange,above] (2.north west) --
(5.north east) -- (5.south east) -- (2.south west) -- cycle;

			\input{graphExample2}
\draw		(2) 	to[out=40,in=140] (5);
 
\node[vertex,ball color=blue,opaque] (2) at (-6.0,3.0) {2};
\node[vertex,ball color=blue,opaque] (7) at (0,3.0) {7};

\draw[very thick,color=red]		(5) 	to[out=145,in=35] (6);
\draw[very thick,color=red]		(5) 	to[out=150,in=30] (7);
\draw[very thick,color=red]		(4) 	-- (5);
\draw[very thick,color=red]		(4) 	-- (6);
\end{tikzpicture}\quad}
        \end{subfigure}
        \begin{subfigure}[{The optimum solution $\{ 4,5,6\}$ of $\max
        \left\{ g_1(x) \mid x_{W_1} = 0 \right\}$ yields
         $\gamma_1 = 1$ and $g_0(x) = g_1(x) + x_{W_1} \leq 3$
        valid for $STAB(G_0)$}.]{ \label{sfig:cl3}
        \quad\begin{tikzpicture}[thick,fill
        opacity=0.5,scale=0.4,font=\scriptsize]
\shade[rounded corners=1ex,fill=orange,above] (2.north west) --
(5.north east) -- (5.south west) to[out=-120,in=30] (1.north east) -- (1.north
west) to[out=150,in=-60] (2.south east) -- cycle;
\shade[rounded corners=1ex,fill=red,above] (1.north west) to[out=150,in=-60]
(2.south east) -- (3.base) -- (3.south) -- cycle;
\node[text=red,text opacity=1] at +(-3,0) {$W_1$}; 

			\input{graphExample2}
\draw		(2) 	to[out=30,in=150] (5);
 
\node[vertex,ball color=red,opaque] (4) at (1.5,0) {4};
\node[vertex,ball color=red,opaque] (6) at (6.0,3.0) {5};
\node[vertex,ball color=red,opaque] (6) at (-3.0,3.0) {6};
\end{tikzpicture}\quad}
        \end{subfigure}\quad\quad
        \begin{subfigure}[{$f_0(x) = f_1(x) \leq 2$ is also
        valid for $F_0$ since $\phi_1 = 0$}.]{		\label{sfig:scl3} 
        \quad\begin{tikzpicture}[thick,fill
        opacity=0.5,scale=0.4,font=\scriptsize]
\shade[rounded corners=1ex,fill=orange,above] (2.north west) --
(5.north east) -- (5.south west) to[out=-120,in=30] (1.north east) -- (1.north
west) to[out=150,in=-60] (2.south east) -- cycle;
\shade[rounded corners=1ex,fill=red,above] (1.north west) to[out=150,in=-60]
(2.south east) -- (3.base) -- (3.south) -- cycle;
\node[text=red,text opacity=1] at +(-3,0) {$W_1$}; 

			\input{graphExample2}
\draw		(2) 	to[out=30,in=150] (5);
 
\node[vertex,ball color=red,opaque] (4) at (1.5,0) {4};
\node[vertex,ball color=red,opaque] (6) at (6.0,3.0) {5};
\node[vertex,ball color=red,opaque] (6) at (-3.0,3.0) {6};
\end{tikzpicture}\quad}
        \end{subfigure}
\caption{Liftings
(\subref{sfig:cl1}--\subref{sfig:cl2}--\subref{sfig:cl3}) and strengthened
liftings (\subref{sfig:scl1}--\subref{sfig:scl2}--\subref{sfig:scl3}) starting
with the clique inequality of $W_4 = \{ 2, 5, 6, 7, 8 \}$ to generate
$x_{\{4,5,6,7,8\}} + 2x_{\{1,2,3\}} \leq 3$, in the former case, and
$x_{\{1,2,4,6,7,8\}} + 2x_{\{3\}} \leq 2$, in the latter case.}
\label{fig:lifting}
\end{figure}
